﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm.Struct
{
    public class LinkList<T> where T :IEquatable<T>
    {
        public LinkList()
        {
        }

        public LinkNode<T> Head
        {
            get;
            private set;
        }

        public bool IsEmpty()
        {
            return null == Head;
        }

        public LinkNode<T> Search(T x)
        {
            LinkNode<T> current = Head;
            while (null != current && !current.Data.Equals(x))
            {
                current = current.NextLinkNode;
            }
            return current;
        }

        public void Insert(LinkNode<T> node)
        {
            node.NextLinkNode = Head;
            if (null != Head)
            {
                Head.PreLinkNode = node;
            }
            Head = node;
            node.PreLinkNode = null;
        }

        public void Delete(LinkNode<T> node)
        {
            //更新前面一个节点的后向指针
            if (null != node.PreLinkNode)
            {
                node.PreLinkNode.NextLinkNode = node.NextLinkNode;
            }
            else //node 如果是头节点
            {
                Head = node.NextLinkNode;
            }

            //更新后面一个节点的前向指针
            if (null != node.NextLinkNode)
            {
                node.NextLinkNode.PreLinkNode = node.PreLinkNode;
            }
        }
    }

    public class LinkNode<T>
    {
        private T _data;
        public LinkNode(T t)
        {
            _data = t;
        }

        public T Data
        {
            get
            {
                return _data;
            }
        }

        public LinkNode<T> PreLinkNode;

        public LinkNode<T> NextLinkNode;
    }
}
